using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using Needle.Utils;

namespace Needle.Core.Activation {

    /// <summary>A
    /// A graphs of dependencies, used to check for dependency cycles.
    /// </summary>
    public class DependencyGraph {

        private Dictionary<InstanceId, bool> memory;
        /// <summary>
        /// Initializes a new instance
        /// </summary>
        public DependencyGraph() {
            m_Vertices = new VertexCollection();

        }

        private bool m_Locked;
        /// <summary>
        /// True if the graph is locked, and cannot be altered.
        /// </summary>
        public bool IsLocked {
            get { return m_Locked; }
            set {
                m_Locked = value;
                m_Vertices.IsLocked = value;
                foreach (Vertex v in m_Vertices) {
                    v.Edges.IsLocked = value;
                }
                if (value) {
                    memory = new Dictionary<InstanceId, bool>();
                } else {
                    memory = null;
                }
            }
        }

        private VertexCollection m_Vertices;
        /// <summary>
        /// The vertices in this graph.
        /// </summary>
        public VertexCollection Vertices {
            get { return m_Vertices; }
        }
        /// <summary>
        /// Creates or gets a new vertex for the id given.
        /// </summary>
        public Vertex CreateOrGetVertex(InstanceId id) {
            CheckLocked();
            Ensure.NotNull(id, "id");
            if (Vertices.Contains(id)) {
                return Vertices[id];
            }
            Vertex vertex = new Vertex(id);
            Vertices.Add(vertex);
            return vertex;
        }
        /// <summary>
        /// Adds an dependency edge that is, a depends on b.
        /// </summary>
        public void AddEdge(InstanceId a, InstanceId b) {
            CheckLocked();
            Ensure.NotNull(a, "a");
            Ensure.NotNull(b, "b");
            Vertex va = Vertices[a];
            Vertex vb = Vertices[b];
            va.Edges.Add(vb);
        }

        /// <summary>
        /// Returns true if the dependency graph is a directed acyclic graph, 
        /// false if there are dependency cycles.
        /// </summary>
        public bool IsDagFor(InstanceId id) {
            return IsDagFor(id, false);
        }
        private void CheckLocked() {
            if (m_Locked) {
                throw new InvalidOperationException(GetType().Name + " is locked");
            }
        }
        /// <summary>
        /// Returns true if the dependency graph is a directed acyclic graph.
        /// returns false or throws an exception if there are dependency cycles.
        /// </summary>
        /// <param name="id">The id</param>
        /// <param name="throwIfCyclic">true if this method should throw an exception, false otherwise.</param>
        /// <returns></returns>
        public bool IsDagFor(InstanceId id, bool throwIfCyclic) {
            Ensure.NotNull(id, "id");
            if (IsLocked) {
                bool result = false;
                if (Recall(id, out result)) {
                    return result;
                }
            }
            Vertex dv = Vertices[id];
            VertexCollection stack = new VertexCollection();
            bool isDag = IsDagFor(stack, dv);
            if (!isDag && throwIfCyclic) {
                StringBuilder sb = new StringBuilder("Cyclic dependency detected: \n");
                foreach (Vertex v in stack) {
                    sb.AppendLine(v.Id.ToString());
                }
                sb.AppendLine(stack[0].Id.ToString());
                throw new CyclicDependencyException(sb.ToString());
            }
            return isDag;
        }

        private bool IsDagFor(VertexCollection stack, Vertex dv) {
            if (IsLocked) {
                bool result = false;
                if (Recall(dv.Id, out result)) {
                    return result;
                }
            }
            if (stack.Contains(dv)) {
                if (IsLocked)
                    Remember(dv.Id, false);
                return false;
            }
            stack.Push(dv);
            foreach (Vertex v in dv.Edges) {
                if (!IsDagFor(stack, v)) {
                    if (IsLocked)
                        Remember(dv.Id, false);
                    return false;
                }
            }
            stack.Pop();
            if (IsLocked)
                Remember(dv.Id, true);
            return true;
        }

        private bool Recall(InstanceId id, out bool result) {
            return memory.TryGetValue(id, out result);
        }

        private void Remember(InstanceId id, bool result) {
            bool oldresult = false;
            if (memory.TryGetValue(id, out oldresult))
                memory[id] = result && oldresult;
            else
                memory.Add(id, result);
        }

        /// <summary>
        /// Defines a vertex in the grap and its dependencies
        /// </summary>
        [DebuggerDisplay("Vertex {Id}")]
        public class Vertex {

            /// <summary>
            /// initializes a new instance
            /// </summary>
            public Vertex(InstanceId id) {
                m_Id = id;
                m_Edges = new VertexCollection();
            }

            private InstanceId m_Id;
            /// <summary>
            /// The id of this vertex
            /// </summary>
            public InstanceId Id {
                get { return m_Id; }
            }

            private VertexCollection m_Edges;
            /// <summary>
            /// The ids this id depends on.
            /// </summary>
            public VertexCollection Edges {
                get { return m_Edges; }
            }

            private object m_Tag;
            /// <summary>
            /// holder for user objects associated with this vertex.
            /// </summary>
            public object Tag {
                get { return m_Tag; }
                set { m_Tag = value; }
            }

        }
        /// <summary>
        /// A keyed collection of vertices.
        /// </summary>
        public class VertexCollection : Needle.Utils.Collections.KeyedCollection<InstanceId, Vertex> {

            /// <summary>
            /// Creates a new instance
            /// </summary>
            public VertexCollection()
                : base(x => x.Id)
            {           }
            /// <summary>
            /// Returns the id for the vertex
            /// </summary>
            protected override InstanceId GetKeyForItem(Vertex item) {
                return item.Id;
            }

            private bool m_Locked;
            /// <summary>
            /// REturns true if this collection is locked., false if not.
            /// </summary>
            public bool IsLocked {
                get { return m_Locked; }
                set { m_Locked = value; }
            }

            /// <summary>
            /// clears the collection
            /// </summary>
            protected override void ClearItems() {
                CheckLocked();
                base.ClearItems();
            }
            /// <summary>
            /// inserts an item into the collection.
            /// </summary>
            protected override void InsertItem(int index, Vertex item) {
                Ensure.NotNull(item, "item");
                CheckLocked();
                base.InsertItem(index, item);
            }
            /// <summary>
            /// removes an item from the collection
            /// </summary>
            protected override void RemoveItem(int index) {
                CheckLocked();
                base.RemoveItem(index);
            }
            /// <summary>
            /// Sets an item in at the index in the collection 
            /// </summary>
            protected override void SetItem(int index, Vertex item) {
                Ensure.NotNull(item, "item");
                CheckLocked();
                base.SetItem(index, item);
            }

            private void CheckLocked() {
                if (m_Locked) {
                    throw new InvalidOperationException(GetType().Name + " is locked");
                }
            }

            internal void Push(Vertex item) {
                Insert(Count, item);
            }

            internal Vertex Pop() {
                int index = Count - 1;
                if (index > -1) {
                    Vertex dv = this[index];
                    RemoveAt(index);
                    return dv;
                }
                throw new InvalidOperationException(GetType().Name + " is empty");
            }
        }
    }
}
